Available as one of the calculation techniques to produce a quotient in a division operation is a “loop operation”. In the loop operation, a subtract operation or an add operation (or only a subtract operation) of a divisor is repeated to a dividend or an interim remainder. Recovery division method, non-recovery division method, and Sweeny-Robertson-Tocher (SRT) division are typical of division operation techniques using the loop operation.
FIG. 25 illustrates a division operation based on the loop operation.
The division operation based on the loop operation is divided into three major processes of a pre-operation 910, a loop operation 920, and a post-operation 930. The loop operation 920 includes a partial quotient calculation operation 921.
In the pre-operation 910, an absolute value operation and a left shift operation modify a data format of a dividend and a divisor on which the loop operation 920 is performed. A loop count is calculated in the partial quotient calculation operation 921 in the loop operation 920. If a divider circuit calculates a partial quotient of 1 bit at each cycle of the partial quotient calculation operation 921, a circuit calculating the loop count of the partial quotient calculation operation 921 is referred to as a “loop counter”. And, the total loop count needed to finish calculating the partial quotient of 1 bit is referred to as a “loop count value”.
The loop count value is calculated based on a leading zero count (LZC) of each of the dividend and the divisor. The LZC refers to the number of continued 0s (“zeros”) from the most significant bit (MSB) of input binary data. LZC_A and LZC_B represent an LZC of the dividend and an LZC of the divisor, respectively, and the loop count value LC is calculated in accordance with the following equation (1):LC=LZC—B−LZC—A+1  (1)
In the loop operation 920, mainly, the partial quotient calculation operation 921 is repeated to calculate a partial quotient of 1 bit. In the partial quotient calculation operation 921, a divisor is added to or subtracted from a dividend or an interim remainder (hereinafter also referred to as addition and subtraction of a divisor). A partial quotient, an interim quotient and an interim remainder are calculated based on a comparison between the results of the addition and subtraction, a loop count is subjected to a subtract operation, and the interim remainder is leftward shifted. In the post-operation 930, the interim quotient calculated in the loop operation 920 is corrected in order to calculate a final quotient.
The loop count value represents a bit width of the final quotient and represents the loop count of the partial quotient calculation operation 921 at the same time. As previously discussed, the loop count is determined from the dividend and the divisor. The loop count value is decremented by 1 each time the partial quotient calculation operation 921 is executed. When the loop count becomes “0”, the loop operation 920 ends.
The interim remainder refers to a value that results from adding a divisor to or subtracting a divisor from a dividend in the partial quotient calculation operation 921. At a first cycle of the partial quotient calculation operation 921, the addition and subtraction of the divisor is performed on the dividend, but at second and subsequent cycles, the addition and subtraction of the divisor is performed on an interim remainder calculated through an immediately preceding partial quotient calculation operation 921. For simplicity of explanation, the addition and subtraction of the divisor in the partial quotient calculation operation 921 is performed on an interim remainder including a dividend.
The partial quotient is a value that results from comparing an interim remainder as a result of the addition and subtraction with a divisor. The interim quotient is a value that results from summing the partial quotients, each partial quotient obtained at each execution of the partial quotient calculation operation 921.
The division operation is expedited by calculating partial quotients of a plurality of bits in a single partial quotient calculation process. In the division operation, the term Radix-2n may be used in accordance with a bit width n of a partial quotient determined in one execution cycle (hereinafter simply referred to as “cycle”) of the partial quotient calculation process. If the radix of an operation in one cycle is 2j in the division of Radix-2n, k add and subtract operations and k comparison operations are performed per cycle. Partial quotients of the n bits (n=j×k, where each of j and k is an integer of 1 or larger) per cycle are thus calculated.
If n≧2, partial quotients of a plurality of bits are calculated per cycle. Unlike the case of n=1, the loop operation is performed in response to a speed responsive to a multiple of n and then the final quotient is calculated. The division operation of calculating the partial quotient of a plurality of bits at a cycle is referred to the “high-radix division method”.
A process of calculating a partial quotient of n bits at a cycle is here referred to as an “n-bit partial quotient calculation operation”. If the n-bit partial quotient calculation operation is performed once with n≧2 and k=1, an operation of comparing the dividend or the interim remainder with the divisor causes partial quotients of j (=n) bits at a time. Each time the comparison operation is performed, n is subtracted from the loop count value.
If the n-bit partial quotient calculation operation is performed once with n≧2 and j=1, the operation of comparing the dividend or the interim remainder with the divisor is performed by k (=n) times in series. One cycle of comparison operation calculates a partial quotient of one bit, and “1” is subtracted from the loop count value. If the comparison operation is performed by k times at one cycle, interim quotients of n bits are thus obtained.
The partial quotients of n bits are determined at one cycle in the Radix-2n division operation. As previously discussed, the loop count value represents the bit width of the final quotient. In the Radix-2n division operation, n is subtracted from the loop count value per cycle. If the initial value of the loop count value is a multiple of n, the loop count value at the end of the loop operation 920 is “0”. If the initial value of the loop count value is not a multiple of n, the loop count value at the end of the loop operation 920 exceeds “0”, becoming a negative value. In such a case, a correct partial quotient may not be calculated in the final n-bit partial quotient calculation operation in the loop operation 920, and the final quotient becomes an erroneous value having a bit width not being n. If the initial value of the loop count value is not a multiple of n, an additional operation illustrated in FIGS. 26 and 27 is performed to have a correct final quotient.
FIG. 26 illustrates a first process example that is applicable if the initial value of the loop count value is not a multiple of n. FIG. 27 illustrates a second process example that is applicable if the initial value of the loop count value is not a multiple of n. In FIGS. 26 and 27, like elements are designated with like reference numerals in FIG. 25.
FIGS. 26 and 27 illustrate a loop operation 920a in which an n-bit partial quotient calculation operation 921a is repeated to calculate partial quotients of n bits. Each time the n-bit partial quotient calculation operation 921a is executed in the loop operation 920a, n is subtracted from the loop count value. The n-bit partial quotient calculation operation 921a is repeated until the loop count value becomes zero or less.
In the first process example, a quotient fix operation 940 may be performed subsequent to the end of the loop operation 920a as illustrated in FIG. 26. The quotient fix operation 940 corrects an interim quotient calculated at this point of time to be a correct value. In the quotient fix operation 940, for example, an operation reverse to the addition and subtraction and the comparison operation in the n-bit partial quotient calculation operation 921a is executed by the same number of times as the number of times by which the addition and subtraction and the comparison operation have been abundantly executed.
The division operation becomes complex, because the quotient fix operation 940 is added. To execute the quotient fix operation 940, a divider circuit further needs a circuit which records necessary information on a process content for the addition and subtraction and the comparison operation in the n-bit partial quotient calculation operation 921a and a circuit which performs the addition and subtraction and the comparison operation in a reverse procedure. Accordingly, the circuit scale of a divider circuit may increase, and power consumption of the divider circuit may increase accordingly, and latency time of the divider circuit may be prolonged.
In the second process example, a remainder fix operation 922 is executed as desired based on the loop count value at the point before executing the n-bit partial quotient calculation operation 921a in the loop operation 920a as illustrated in FIG. 27. A particular process may be performed on the value of the interim remainder in the remainder fix operation 922. For example, the comparison results may not be reflected in the output process of the interim remainder when the loop count value is less than n at a point of time.
Similarly to the first process example, the division operation becomes complex in the second process example, because the remainder fix operation 922 is added. In the divider circuit, a circuit performing the remainder fix operation 922 needs to be included in a circuit performing the loop operation 920a. For this reason, the circuit performing the remainder fix operation 922 operates regardless of the current loop count value each time the n-bit partial quotient calculation operation 921a is performed. Not only the divider circuit becomes large in scale but also power is further consumed by otherwise unnecessary operation if the current loop count value is n or larger. If the final remainder is output in the middle of the loop operation 920a, a circuit such as a selector may further be arranged as a data path to exit the loop operation 920a. 
In one example of division operation, the dividend and the divisor are shifted in the pre-operation such that a difference between the number of shifts of dividend and the number of shifts of divisor becomes a multiple of n. The number of bits calculated by the divider circuit thus becomes a multiple of n. In another example of division operation, an amount of division operation is intended to be reduced per bit. In this example of division operation, a divisor is shifted leftward by 16 bits, and “1” is subtracted from the shifted divisor. A resulting value is used in the loop operation.
A typical system is described Japanese Laid-open Patent Publication No. 4-291418.